package com.agile.leetcode.easy.luckynum;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 在整数数组中，如果一个整数的出现频次和它的数值大小相等，我们就称这个整数为「幸运数」。
 *
 * 给你一个整数数组 arr，请你从中找出并返回一个幸运数。
 *
 * 如果数组中存在多个幸运数，只需返回 最大 的那个。
 * 如果数组中不含幸运数，则返回 -1 。
 *  
 *
 * 示例 1：
 *
 * 输入：arr = [2,2,3,4]
 * 输出：2
 * 解释：数组中唯一的幸运数是 2 ，因为数值 2 的出现频次也是 2 。
 * 示例 2：
 *
 * 输入：arr = [1,2,2,3,3,3]
 * 输出：3
 * 解释：1、2 以及 3 都是幸运数，只需要返回其中最大的 3 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-lucky-integer-in-an-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author:ChenZhangKun
 * @Date: 2021/2/28 14:26
 */
public class LuckyNum {
    public static void main(String[] args) {
        LuckyNum luckyNum=new LuckyNum();
        int[] arr={19,12,11,14,18,8,6,6,13,9,8,3,10,10,1,10,5,12,13,13,9};
        int lucky = luckyNum.findLucky(arr);
        System.out.println(lucky);
    }
    public int findLucky(int[] arr){
        // 定义map，判断是否重复
        Map<Integer,Integer> map=new HashMap<>();
        // 定义集合接收重复数
        Set<Integer> set=new HashSet<>();
        // 循环
        for (int i : arr) {
            if (map.containsKey(i)){
                // 得到count
                Integer count = map.get(i);
                count+=1;
                if (i==count){
                    // 加入集合
                    set.add(i);
                }else {
                    if (set.size()>0&&set.contains(i)){
                        set.remove(i);
                    }
                }
                map.put(i,count);
            }else {
                map.put(i,1);
                if (i==1) set.add(i);
            }
        }
        // 排序
        List<Integer> collect = set.stream().sorted(Comparator.reverseOrder()).collect(Collectors.toList());
        if (collect.size()>0){
            return collect.get(0);
        }else {
            return -1;
        }
    }
}
